package algorithm.leetcode;

public class LeetCode_204_countPrimes {
    /**埃氏筛法
     *做法：做法其实很简单，首先将2到n范围内的整数写下来，其中2是最小的素数。
     *     将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。
     *     再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。
     *     然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是O(nloglogn)。
     *
     *题解：如果要是按照一个一个判断是否是素数然后把ans+1，时间复杂度为O(n√n)，
     *      对于10^6的数据时间复杂度就是O(10^9)，必定会超时，但此时埃氏筛法的时间复杂度只有O(nloglogn)。
     */
    public int countPrimes(int n) {
        if (n < 2) return 0;
        int[] prime = new int[n + 1];
        //数组表中 素数为0 非素数为1
        prime[0] = prime[1] = 1;
        int ans = 0;
        for (int i = 2; i < n; i++) {
            //若当前数非素数->跳过
            if (prime[i] == 1) continue;
            //位运算 平方 将所有i的倍数置为1->必定是非素数
            for (int j = i << 1; j < n; j += i){
                prime[j] = 1;
            }
            //结果+1
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) {

    }
}
